A finite state machine is a representation of an event-driven (reactive) system. In a finite state machine, a system makes a transition from one state to another provided that the condition defining the transition is true. A finite state machine may be described using a state transition table. A state transition table is a truth table describing the relationships among the inputs, outputs, and states of a finite state machine. Hence, the state transition table describes the behavior of a system given specific inputs. Alternatively, the behavior of a system may be described in terms of transitions among states. A state's activity is determined based on the occurrence of certain events under certain conditions. Additionally, a finite state machine may be graphically represented by a state diagram. A state diagram is a directed graph that illustrates transitions of one state to another. Stateflow® of MathWorks, Inc. from Natick, Mass. is an example of a technical computing software application that utilizes state diagrams to represent a finite state machine.
Stateflow® is an interactive simulation and code generation tool for event-driven systems. Stateflow® enables the representation of hierarchical states. States may be organized within other higher-level states forming a parent/offspring structure that may be used to describe complex systems. Additionally, Stateflow® allows the representation of parallel states. Hence, two or more states within the same hierarchy level may be active at the same time. Stateflow® further provides the functionalities to specify a destination state of a transition based on historical information. Stateflow® processes states and events in a top-down processing manner. In other words, Stateflow® processes states and events from the top of the hierarchy and works its way down the hierarchy. A state is processed only if it is active. If a state is active, its superstate (parent state) must also be active as well.
In Stateflow®, events drive the Stateflow® diagram execution. The occurrence of an event causes the status of the states in the Stateflow® diagram to be evaluated and often causes a transition to take place. Specifically, an event may be broadcast to trigger a transition to occur. Additionally, the broadcast of an event may also trigger an action to be executed. An action may be a function call, a broadcast event, a variable assignment, etc. An action may be executed as part of a transition from one state to another, or based on a status of a state. A transition can have either a condition action or a transition action. A condition action is executed as soon as the condition is evaluated to true but before the transition takes place. A transition action is executed after the transition takes place.
As mentioned above, Stateflow® uses a top-down processing scheme to process events and states. Specifically, when an event occurs, Stateflow® processes from the top or root of the Stateflow® state diagram down through the hierarchy of the diagram. A disadvantage of the current top-down processing implementation of Stateflow® is that it may encounter certain cyclic behaviors. An example is given with respect to FIG. 1. FIG. 1 illustrates a state chart 100 containing state 102 and state 104. State 104 further contains state 106 and state 108. Transition 100a is the default transition into state 102, which is taken when state chart 100 first becomes active. Transition 100c is the default transition into state 106, which is taken when state 104 first becomes active. Transitions 110b, 110d, and 110e are transitions from one state to another. At a certain point in time, assuming that state 108 broadcasts an error event to its parent state 104 using a send( ) function call and because Stateflow® utilizes top-down processing, the processing of the send( ) function call starts at state 104 as opposed to starting with state 106 or state 108. If state 104 does not know how to process the error event sent by the send( ) function call, then state 104 passes the error event to its active child state 108. However, state 108 cannot process this error event, and state 108 again sends the error event via a send( ) function call to its parent state 104. A cyclic behavior hence occurs. A method is needed to avoid cyclic behavior, especially when a parent state asks its child state to handle an event that the child state already knows it cannot handle. Therefore, Stateflow®'s top-down approach does not always make a finite state machine model work as expected. However, Stateflow®'s top-down approach simplifies the Stateflow® diagram by looking at the transitions out of the superstate without considering all the details of its substates and their transitions.
The Unified Modeling Language™ of Object Management Group® allows one to generate models using state diagrams. UML processes states and events in such state diagrams in a bottom-up processing manner. One of ordinary skill in the art will appreciate that bottom-up processing performs error handling better than top-down processing. However, for a superstate to make a transition to another state in a bottom-up processing environment, all the substates and their transitions must be evaluated and considered before the superstate may make a transition. Hence, some processing power is wasted on unnecessary executions of substates and transition or an undesirable transition may be made by a substate.